class Solution {
public:
    int findDuplicate(vector<int>& nums)
    {
        int n = nums.size();
        int left = 1, right = n - 1;

        while (left < right)
        {
            int mid = (left + right) / 2;
            int count = 0;
            for (auto e : nums)
            {
                if (e <= mid) count++;
            }
            if (count > mid) right = mid;
            else left = mid + 1;
        }
        return left;
    }
};

class Solution {
public:
    void nextPermutation(vector<int>& nums)
    {
        int n = nums.size();
        int i = n - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) i--;

        if (i == 0) reverse(nums.begin(), nums.end());
        else
        {
            for (int j = n - 1; j >= i; j--)
            {
                if (nums[j] > nums[i - 1])
                {
                    swap(nums[i - 1], nums[j]);
                    break;
                }
            }
            reverse(nums.begin() + i, nums.end());
        }

    }
};

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int left = -1, right = nums.size();
        for (int i = 0; i < right; )
        {
            if (nums[i] == 0) swap(nums[i++], nums[++left]);
            else if (nums[i] == 1) i++;
            else swap(nums[i], nums[--right]);
        }
    }
};